//1143.最长公共子序列
//https://leetcode.cn/problems/longest-common-subsequence/?envType=study-plan-v2&envId=top-100-liked
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        //dp[m][n]表示 text1[0,m] 和 text2[0,n] 区间内的最长公共子序列
        int m = text1.size(),n = text2.size();
        vector<vector<int>> dp(m+1,vector<int>(n+1));
        for(int i = 1;i<=m;++i)
            for(int j = 1;j<=n;++j)
            {
                if(text1[i-1] == text2[j-1]) dp[i][j]=dp[i-1][j-1]+1;
                else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        return dp[m][n];
    }
};